package algocasts;

public class P56_SingleNumInSortedArray {
    // Time:O(n) Space:O(1)
    public int SingleNumInSortedArray(int[] nums) {
        int result = 0;
        for (int num : nums) result ^= num;
        return result;
    }

    // Time:O(log(n)) Space:O(1)
    public int SingleNumInSortedArrayBinarySearch(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            // 如果左边的数等于中间指针指向的数  中间指针指向左边
            if (mid - 1 >= 0 && nums[mid - 1] == nums[mid]) mid -= 1;
                // 如果右边的数等于中间指针指向的数，不动
            else if (mid + 1 < nums.length && nums[mid + 1] == nums[mid]) {
                // 如果左右两边都不相等，则是单身数字 直接返回
            } else return nums[mid];
            // 如果左边和中间之间的数是奇数个，则单身数字在这之间
            if ((mid - low) % 2 == 1) high = mid - 1;
                // 否则在中间和右边之间
            else low = mid + 2;
        }
        return -1;
    }
}
